#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <memory>
#include <limits>
using namespace std;

void find_vec16_max(short* data,  short *max_data, unsigned short* pot_index_of_max_data, int length)
{
	if (length != 16)
	{
		cout << "find_vec16_max error" << endl;
		return;
	}
	short max = (numeric_limits<short>::min)();
	unsigned short index = 0;
	for (int i = 0; i < 16; i++)
	{
		if (data[i]>max)
		{
			max = data[i];
			index = i;
		}
	}
	*max_data = max;
	*pot_index_of_max_data = (1 << index);
}

unsigned short convert_to_cnt(unsigned short index)
{
	for (int i = 0; i < 16; i++)
	{
		int bit_flag = (index >> i) & 0x0001;
		if (bit_flag)
		{
			return i;
		}
	}
	return 0xffff;
}
void pot_index_to_cnt(unsigned short* pot_index, unsigned short* cnt_index, int length)
{
	if (length != 16)
	{
		cout << "pot_index_to_cnt error" << endl;
		return;
	}
	for (int i = 0; i < 16; i++)
	{
		cnt_index[i] = convert_to_cnt(pot_index[i]);
	}
}

#define align_up_16(x) ((x+15)&(~0xf))

int sort_data(unsigned char* data_in,
	unsigned char* topk_data_out, unsigned short* topk_index_out,
	int topk, int element_nums)
{
	int unsort_data_length_1 = align_up_16(element_nums);//max:4096
	int unsort_data_length_2 = align_up_16(unsort_data_length_1 / 16);//max:256
	int unsort_data_length_3 = align_up_16(unsort_data_length_2 / 16);//max:16

	int loop_nums_1 = unsort_data_length_1 / 16;//max 256
	int loop_nums_2 = unsort_data_length_2 / 16;//max 16
	int loop_nums_3 = 1;// max 1

	unique_ptr<short[]>	unsort_data_1(new short[unsort_data_length_1]);
	unique_ptr<short[]>	unsort_data_2(new short[unsort_data_length_2]);
	unique_ptr<short[]>	unsort_data_3(new short[unsort_data_length_3]);

	unique_ptr<unsigned short[]> sort_index_1(new unsigned short[loop_nums_1]);
	unique_ptr<unsigned short[]> sort_index_2(new unsigned short[loop_nums_2]);

	unique_ptr<unsigned short[]> convert_pot(new unsigned short[16]);
	unique_ptr<unsigned short[]> convert_cnt(new unsigned short[16]);

	short* unsort_data_buffer_1 = unsort_data_1.get();
	short* unsort_data_buffer_2 = unsort_data_2.get();
	short* unsort_data_buffer_3 = unsort_data_3.get();
	unsigned short* sort_index_buffer_1 = sort_index_1.get();
	unsigned short* sort_index_buffer_2 = sort_index_2.get();
	unsigned short* convert_pot_buffer = convert_pot.get();
	unsigned short* convert_cnt_buffer = convert_cnt.get();

	int base_shift = unsort_data_length_1 - 16;
	for (int k = 0; k < 16; k++)
	{
		unsort_data_buffer_1[base_shift + k] = (numeric_limits<short>::min)();
	}
	base_shift = unsort_data_length_2 - 16;
	for (int k = 0; k < 16; k++)
	{
		unsort_data_buffer_2[base_shift + k] = (numeric_limits<short>::min)();
	}
	base_shift = unsort_data_length_3 - 16;
	for (int k = 0; k < 16; k++)
	{
		unsort_data_buffer_3[base_shift + k] = (numeric_limits<short>::min)();
	}

	//1.load data and convert short
	for (int i = 0; i < element_nums; i++)
	{
		unsort_data_buffer_1[i] = data_in[i];
	}

	for (int k = 0; k < topk; k++)
	{
		short* unsort_data_buffer_1_base = unsort_data_buffer_1;

		short currnet_slice_max_data_a;
		unsigned short currnet_slice_pot_index_of_max_data_a;

		for (int i = 0; i < loop_nums_1; i++)
		{
			find_vec16_max(unsort_data_buffer_1_base, &currnet_slice_max_data_a, &currnet_slice_pot_index_of_max_data_a, 16);

			unsort_data_buffer_2[i] = currnet_slice_max_data_a;
			sort_index_buffer_1[i] = currnet_slice_pot_index_of_max_data_a;

			unsort_data_buffer_1_base += 16;
		}

		short* unsort_data_buffer_2_base = unsort_data_buffer_2;
		for (int i = 0; i < loop_nums_2; i++)
		{
			find_vec16_max(unsort_data_buffer_2_base, &currnet_slice_max_data_a, &currnet_slice_pot_index_of_max_data_a, 16);

			unsort_data_buffer_3[i] = currnet_slice_max_data_a;
			sort_index_buffer_2[i] = currnet_slice_pot_index_of_max_data_a;

			unsort_data_buffer_2_base += 16;
		}

		find_vec16_max(unsort_data_buffer_3, &currnet_slice_max_data_a, &currnet_slice_pot_index_of_max_data_a, 16);

		topk_data_out[k] = (unsigned char)currnet_slice_max_data_a;

		convert_pot_buffer[0] = currnet_slice_pot_index_of_max_data_a;
		pot_index_to_cnt(convert_pot_buffer, convert_cnt_buffer, 16);

		int n3_cnt_local = convert_cnt_buffer[0];
		int n3_cnt_global = n3_cnt_local;

		convert_pot_buffer[0] = sort_index_buffer_2[n3_cnt_global];
		pot_index_to_cnt(convert_pot_buffer, convert_cnt_buffer, 16);

		int n2_cnt_local = convert_cnt_buffer[0];
		int n2_cnt_global = n2_cnt_local + n3_cnt_global * 16;

		convert_pot_buffer[0] = sort_index_buffer_1[n2_cnt_global];
		pot_index_to_cnt(convert_pot_buffer, convert_cnt_buffer, 16);

		int n1_cnt_local = convert_cnt_buffer[0];
		int n1_cnt_global = n1_cnt_local + n2_cnt_global * 16;

		topk_index_out[k] = n1_cnt_global;

		unsort_data_buffer_1[n1_cnt_global] = -1;
	}
	return 1;
}

bool cmp(pair<unsigned char, unsigned short> a, pair<unsigned char, unsigned short> b)
{
	return a.first > b.first;
}
int test_sort()
{
	const int element_nums = 200;
	const int topk = 30;

	unique_ptr<unsigned char> data_in_ptr(new unsigned char[element_nums]);
	unique_ptr<unsigned char> sort_data_ptr(new unsigned char[topk]);
	unique_ptr<unsigned short> sort_index_ptr(new unsigned short[topk]);

	unsigned char* data_in_array = data_in_ptr.get();
	unsigned char* sort_data_array= sort_data_ptr.get();
	unsigned short* sort_index_array= sort_index_ptr.get();

	vector<unsigned char> init_data(element_nums);
	for (int i = 0; i < element_nums; i++)
	{
		init_data[i] = i;
	}
	unique_ptr<pair<unsigned char, unsigned short>> data_sort(new pair<unsigned char, unsigned short>[element_nums]);

	int count = element_nums;
	for (int i = 0; i < element_nums; i++)
	{
		int rand_index = rand() % count;
		data_in_array[i] = init_data[rand_index];

		data_sort.get()[i].first = init_data[rand_index];
		data_sort.get()[i].second = i;

		init_data.erase(init_data.begin() + rand_index);
		count--;
	}

	sort_data(data_in_array, sort_data_array, sort_index_array, topk, element_nums);

	std::sort(data_sort.get(), data_sort.get() + element_nums, cmp);

	for (int i = 0; i < topk; i++)
	{
		if (data_sort.get()[i].first != sort_data_array[i])
		{
			cout << "result data error" << endl;
			return 0;
		}
		if (data_sort.get()[i].second != sort_index_array[i])
		{
			cout << "result index error" << endl;
			return 0;
		}
	}
	return 1;
}
int test_generate()
{
	const int element_nums = 39;
	for (int k = 0; k < 10; k++)
	{
		unique_ptr<unsigned char> data_ptr(new unsigned char[element_nums]);
		unsigned char* data_in_array = data_ptr.get();

		vector<unsigned char> init_data(element_nums);

		unsigned char rand_base = rand() % 256;
		for (int i = 0; i < element_nums; i++)
		{
			init_data[i] = i + rand_base;
		}
		int count = element_nums;
		for (int i = 0; i < element_nums; i++)
		{
			int rand_index = rand() % count;
			data_in_array[i] = init_data[rand_index];

			init_data.erase(init_data.begin() + rand_index);
			count--;
		}

		for (int i = 0; i < element_nums; i++)
		{
			cout << (unsigned int)data_in_array[i] << " ";
		}
		cout << endl;
	}

	return 1;
}
int main()
{
	if (!test_sort())
		system("pause");
	test_generate();
}